Edit Distance

題目

給你兩個字串（$1\leq$ 長度 $\leq 5000$），有三種操作：

1. 可以在任意字串中任意位置插入一個字元。
2. 可以在任意字串中刪除任意一個字元。
3. 可以在任意字串中將一個字元取代成另一個字元。

求最少經過幾次操作，可以使兩個字串變的一模一樣。

輸入

共兩行，一行一個只含大寫字母的字串。

輸出

一個整數，代表最少的操作數。

範例測資

Input :
LOVE
MOVIE

Output :
2

想法：相同的部分盡量沿用

字串距離系列有很多種，常見的有：萊文斯坦距離（這題）、 LCS 距離（只能刪除和加入）、漢明距離（只能取代）。

第一次看這題會沒什麼頭緒，所以我們先考慮一些簡單的狀況，拿其中一個長度 $n$ 的字串 $s_1$ 去和另一個長度 $m$ 的字串 $s_2$ 配對，此時有三個問題：

1. 要從 $s_2$ 的哪個字開始配對 $s_1$ ？
2. 中間相同的字直接配對一定是好的嗎？
3. 哪些字要選擇跳過或取代？

對於 1. 我們可以選擇全部試試看。
對於 2. 假設兩個字串是 ABBCD 和 ABCD ，顯然跳過一個字會更好。
對於 3. 似乎沒有直接能看出來的好解法。

此時，我們可以反過來考慮，不要想每個字要被放在哪裡，改想每個位置要放哪個字（這種觀察偏難，但在各種題目中，反著想常常都有神奇的效果），也就是考慮某字串的第 $i$ 個字要做甚麼操作。

當然，我們還要考慮現在另一個字串配到哪裡了，畢竟第 $i$ 個字 去配對另一個字串前 $2$ 個字的答案，和前 $5$ 個字的答案顯然不一樣。

問題就變成了：

1. 這一項選擇放某個字串的開頭，此時另一個字串前面都得刪掉，成本是另一個字串到這一項的長度。
2. 這一項選擇刪除一個字，若現在要刪掉某字串的第 $i$ 個字，成本相當於某字串的前 $i-1$ 個字所花的成本，加上刪除這個動作所花的成本 $1$ 。
3. 這一項選擇增加一個字，若現在要在某字串的第 $i$ 個字插一個字，相當於把另一個字串的第 $j$ 個字配對了一樣的東西，效果和直接把第 $j$ 個字刪掉一樣，所以其實刪除和增加是同一件事，只是刪在兩個不同的字串上。
4. 如果兩個字一樣，將他們配對，成本是兩邊各少一個字的成本。不一樣則修改為一樣的，成本是兩邊各少一個字的成本加 $1$ 。

在這四個操作中選擇最小值，而對於最後的答案，只要算出 $s_1$ 配到第 $n$ 個位置且 $s_2$ 配到第 $m$ 個位置的時候最小成本是多少就好了。 同時觀察到操作 1. 可以直接算出，操作 2. 在兩個字串分別配到第 $i$ 個字和第 $j$ 個字時，只跟配到 $i,j-1$ 和 $i-1,j$ 兩個狀態有關，操作 4. 在 $i,j$ 時只跟 $i-1,j-1$ 有關，而且如果相同，他一定是最小的值，因此這是一道二維 dp 的題目，可以用迴圈跑過 $i,j$ 由小到大算出來，時間和空間複雜度都是 $O(nm)$ 。

$dp_{i,j}=\left\{\begin{aligned}&\max(i,j)&\text{if}\min(i,j)=0\\&min(dp_{i-1,j}+1,dp_{i,j-1}+1,dp_{i-1,j-1}+(s_1[i-1]!=s_2[j-1]))&\text{otherwise}\end{aligned}\right.$

範例程式碼

使用 1 base 避免 $i-1$ 或 $j-1$ 會超過陣列範圍，因此正在考慮的文字會在 $i-1,j-1$ 的位置。

C++ 範例

#include <bits/stdc++.h>
using namespace std;
char s1[5005], s2[5005];
int dp[5005][5005]={0};
int main(){
    cin >> s1 >> s2;
    int i, n = strlen(s1), j , m = strlen(s2);
    for(i = 0; i <= n; ++i) dp[i][0] = i;
    for(j = 0; j <= m; ++j) dp[0][j] = j;
    for(i = 1; i <= n; ++i) {
        for(j = 1; j <= m; ++j) {
            if(s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
        }
    }
    cout << dp[n][m];
}